The invention generally relates to a method and apparatus for optimizing the routing of connections in communications networks. More specifically, the network optimization involves re-routing the paths of established calls in order to optimize one or more path characteristics, such as cost, of individual calls.
In some circuit switched networks established connections may last on average only a few minutes. For instance, in public telephone networks this may be the case with typical voice calls. Consequently, the average voice call may reserve or lock up network resources for only a short time so that, in aggregate, the network resources are continuously being recycled between calls being released and those being established. However, the average call in digital communication networks typically lasts much longer. Calls in such digital networks often carry data traffic. The longevity of these calls means that network resources are tied up for much longer, making it important to select efficient connection paths in order to efficiently utilize network resources.
The calls associated with digital communication networks can assume a variety of forms. For instance, switched connections in an Asynchronous Transfer Mode (ATM) network include switched virtual circuits (SVCs) and soft permanent virtual circuits (SPVCs). These calls are set-up and torn down on demand via a signalling protocol. SVCs are initiated by end-users and signalled between originating and terminating end-user stations. SPVCs are initiated by the network administrator in order to dynamically establish a path between ingress and egress nodes or exchanges using the signalling infrastructure of the network. The connections between end-user equipment and the network are manually configured and remain active until terminated by the network administrator. SPVCs resemble permanent connections but are often preferred thereover because the network can typically provide faster fault restoration capabilities (e.g., in the event of link failure) than a central management authority. In any event, SPVCs can often have a very long life, comprising many months.
Path efficiency, and hence network optimization, can also assume a variety of forms or goals. In some instances, it may be desirable to minimize the cost or administrative weight of calls; or to use paths which feature packet transfer delays as close to maximum pre-specified limits established for calls. These are examples of economic efficiencies. In other instances, it may be desirable to minimize packet or cell loss ratios; to use paths with the least number of nodes and/or links; or to use paths which are least bandwidth-constrained. These are examples of performance efficiencies.
Most networks typically attempt to establish an efficientxe2x80x94albeit not necessarily the most optimalxe2x80x94path for a call when the call is initially established. However, the problem of finding an efficient path is exacerbated in networks which employ hierarchical map-based routing protocols, an example of which is the ATM PNNI protocol described in The ATM Forum Technical Committee, xe2x80x9cPrivate Network-Network Interface Specification Version 1.0xe2x80x9d, doc. no. af-pnni-0055.000, March 1996, which is incorporated by reference herein. In such networks, predetermined groups of nodes or exchanges are generally represented as a single logical group node (LGN) to an external node (located outside of the group). This logical group node is an abstract representation of the topology of the corresponding group of physical nodes. As such, the logical group node can only provide a summary of the nodal and link characteristics of the corresponding physical topology to the external node. This form of topology aggregation is recursively repeated in a hierarchical manner such that logical group nodes at higher levels of the hierarchy represent a more and more summarized view of the nodal and link characteristics of the underlying physical topology to other nodes. In this manner, a call originating node only has to specify a hierarchically complete route to set up a call, leaving the detailed routing decision across a logical group node up to the entry switching system of the group of physical nodes represented by the logical group node. This hierarchical arrangement was designed in order to achieve scaling in large networks and support the source routing of calls.
The net result, however, is that when an originating node or exchange is required to route a call using a hierarchical routing protocol it can only base its routing decision (to determine the most optimal path) at set-up time using summarized nodal and link characteristics. Depending on how many levels the hierarchy in question comprises, the summarized nodal and link characteristics along the hierarchical path selected by the originating exchange may vary significantly from the characteristics of the actual path assumed by the call. This, then, poses a problem in terms of selecting an efficient path for each call, and hence optimizing the network in the aggregate, in the first instance. Moreover, even if an acceptably efficient path for a call is selected in the first instance, network utilization evolves over time. A more efficient path for the call may exist at some later time.
Broadly speaking, one aspect of the invention provides a method of optimizing path selection in a communications network. The method involves selecting an established call routed across the network from an originating exchange to a destination exchange over an established path. This established path will have at least one path metric of interest associated therewith. A second connection path to the destination exchange from the originating exchange is identified which features one or more improved path metrics. This second path is made operative and the call is directed thereover. Thereafter, the first connection path may be cleared. The process may be repeated for each call originating at each node in the network.
The step of identifying the second connection path may involve:
(a) signaling a first message from the originating exchange to the destination exchange over a replacement connection path, wherein the first message incorporates at least one reporting field and each exchange propagating the first message updates the reporting field(s) until it specifies the path metric(s) of the replacement connection path;
(b) signaling a second message incorporating the reporting field(s) back to the originating exchange from the destination exchange.
The replacement connection path is selected as the second connection path provided that either:
(a) the originating exchange checks whether the replacement connection path features an improved actual path metric(s) by testing the value of the received reporting field(s) against the actual path metric(s) of the first connection path, or
(b) a desired connection path metric value(s) is included in the first message and the network is configured to clear back the first message to the originating exchange in the event the network is unable to identify any connection path to the destination exchange satisfying the desired path metric(s).
The invention also discloses a method for optimizing path selection in a communications network, having a plurality of interconnected exchanges, which involves:
(a) selecting an established call, the call being associated with a path metric(s) of interest and routed across the network from an originating exchange to a destination exchange over a first connection path featuring an actual path metric(s);
(b) signaling a first message to the destination exchange from the originating exchange over a second connection path, wherein the message incorporates a reporting field(s) and each exchange propagating the message updates the reporting field(s) until it specifies the actual path metric;
(c) signaling a second message incorporating the reporting field(s) back to the originating exchange from the destination exchange;
(d) directing the call over the second connection path provided it features an improved actual path metric(s); and
(e) thereafter dismantling the first connection path.
The invention also discloses a method for optimizing path selection in a communications network having a plurality of interconnected exchanges, which involves:
(a) selecting an established call, the call being routed across the network from an originating exchange to a destination exchange over a first connection path which is associated with a path metric of interest;
(b) signaling a call set-up message from the originating exchange to the destination exchange over the network, wherein the call set-up message incorporates a desired connection path metric value and a corresponding reporting field, and wherein each exchange propagating the call set-up message updates the reporting field;
(c) clearing back the call set-up message in the event the network is unable to identify any connection path to the destination exchange satisfying the desired path metric, and signaling a connect message back to the originating exchange from the destination exchange in the event the network is able to identify a connection path satisfying the desired path metric;
(d) directing the call over the second connection path; and
(e) thereafter dismantling the first connection path.
According to another aspect of the invention there is provided a method of establishing calls in an ATM network running, PNNI, comprising:
(a) assigning an administrative weight to each physical network element belonging to a predefined type of topological element;
(b) signaling a call set-up message to a destination exchange from an originating exchange over a connection path, wherein the call set-up message incorporates a cumulative administrative weight reporting field and each transiting exchange propagating the call set-up message adds the pre-provisioned administrative weights of topological elements associated therewith until the reporting field specifies the cumulative administrative weight of the connection path;
(c) establishing bearer channel cross-connections on the nodes traversing the connection path; and
(d) signaling a connect message incorporating the reporting field back to the originating exchange from the destination exchange.